718E - Matvey's Birthday - CodeForces Solution

// Hydro submission #63f5c20e8b5dbbf7612bbdc0@1677050383163
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
char s[100005];
int a[100005];
int vis[100005],viscol[8];
int f[100005][8],g[8][8];
int num[8][1<<8];
vector<int> vec[8];
queue<int> que;
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)a[i]=s[i]-'a',vec[a[i]].push_back(i);
	memset(f,0x3f,sizeof(f));
	memset(g,0x3f,sizeof(g));
	for(int i=0;i<8;i++){
		memset(vis,0,sizeof(vis));
		memset(viscol,0,sizeof(viscol));
		for(int j:vec[i])f[j][i]=0,vis[j]=1,que.push(j);
		g[i][i]=0;viscol[i]=1;
		while(!que.empty()){
			int x=que.front();que.pop();
			if(x>1&&!vis[x-1])f[x-1][i]=f[x][i]+1,vis[x-1]=1,que.push(x-1);
			if(x<n&&!vis[x+1])f[x+1][i]=f[x][i]+1,vis[x+1]=1,que.push(x+1);
			if(!viscol[a[x]]){
				viscol[a[x]]=1;g[a[x]][i]=f[x][i];
				for(int y:vec[a[x]])if(!vis[y])f[y][i]=f[x][i]+1,vis[y]=1,que.push(y);
			}
		}
	}
	int ans1=0;ll ans2=0;
	for(int i=1;i<=n;i++)
		for(int j=max(1,i-15);j<i;j++){
			int mn=i-j;
			for(int k=0;k<8;k++)mn=min(mn,f[i][k]+f[j][k]+1);
			if(mn==ans1)ans2++;
			else if(mn>ans1)ans1=mn,ans2=1;
		}
	for(int i=17;i<=n;i++){
		int sta=0;
		for(int j=0;j<8;j++)if(f[i-16][j]-g[a[i-16]][j])sta|=(1<<j);
		num[a[i-16]][sta]++;
		for(int j=0;j<8;j++)
			for(int k=0;k<(1<<8);k++)
				if(num[j][k]){
					int mn=0x3f3f3f3f;
					for(int l=0;l<8;l++)mn=min(mn,f[i][l]+g[j][l]+((k>>l)&1)+1);
					if(mn==ans1)ans2+=num[j][k];
					else if(mn>ans1)ans1=mn,ans2=num[j][k];
				}
	}
	printf("%d %lld\n",ans1,ans2);
	return 0;
}